package exercises.newcoder.solution;

import java.util.Comparator;
import java.util.HashMap;
import java.util.PriorityQueue;

/**
 * <a href="https://www.nowcoder.com/practice/fd711bdfa0e840b381d7e1b82183b3ee?tpId=188&&tqId=38637&rp=1&ru=/activity/oj&qru=/ta/job-code-high-week/question-ranking">
 * NC97 字符串出现次数的TopK问题</a>
 *
 * @author or2
 * @date 2021/8/7 12:38
 */
public class TopKstrings {
    /**
     * return topK string
     *
     * @param strings string字符串一维数组 strings
     * @param k       int整型 the k
     * @return string字符串二维数组
     */
    public String[][] topKstrings(String[] strings, int k) {

//        统计字符串出现次数
        HashMap<String, Integer> map = new HashMap<>();
        for (String string : strings) {
            map.put(string, map.getOrDefault(string, 0) + 1);
        }

//        利用 堆排序(小顶), 获得最大k个元素
        Comparator<Node> nodeComparator = (Node o1, Node o2) -> o2.weight == o1.weight ? o2.string.compareTo(o1.string) : (o1.weight < o2.weight) ? -1 : ((o1.weight == o2.weight) ? 0 : 1);
        PriorityQueue<Node> priorityQueue = new PriorityQueue<>(k, nodeComparator);
        map.forEach((string, weight) -> {
            Node node = new Node(string, weight);
            if (priorityQueue.size() < k) {
                priorityQueue.add(node);
            } else if (nodeComparator.compare(priorityQueue.peek(), node) < 0) {
                priorityQueue.poll();
                priorityQueue.add(node);
            }
        });

        String[][] ans = new String[k][2];
        for (int i = k - 1; i >= 0; i--) {
            Node poll = priorityQueue.poll();
            ans[i][0] = poll.string;
            ans[i][1] = String.valueOf(poll.weight);
        }

        return ans;
    }

    private static class Node {
        public String string;
        public int weight;

        public Node(String string, Integer weight) {
            this.string = string;
            this.weight = weight;
        }
    }
}
